//
//  Problem392.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 392. 判断子序列
 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 进阶：
    如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
 致谢：
 特别感谢 @pbrother 添加此问题并且创建所有测试用例。
 示例 1：
     输入：s = "abc", t = "ahbgdc"
     输出：true
 示例 2：
     输入：s = "axc", t = "ahbgdc"
     输出：false
 提示：
     0 <= s.length <= 100
     0 <= t.length <= 10^4
     两个字符串都只由小写字符组成。
 */
@objcMembers class Problem392: NSObject {
    func solution() {
        print(isSubsequence("abc", "ahbgdc"))
        print(isSubsequence("axc", "ahbgdc"))
    }
    
    /*
     双指针：
     1: 创建一个指针i 指向s，创建一个指针j 指向t
     2: 如果s[i] == t[j] i++ j++
     3: 不相等 j++
     */
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        let sCharts = Array(s)
        let tCharts = Array(t)
        var i = 0
        var j = 0
        while i < sCharts.count, j < tCharts.count {
            if sCharts[i] == tCharts[j] {
                i += 1
                j += 1
            } else {
                j += 1
            }
        }
        
        return i == sCharts.count
    }
}
